#include "Segment.h"
#include "LKH.h"
#include "Sequence.h"

/*
 * The BestKOptMove function makes edge exchanges. If possible, it makes a
 * r-opt move (r >= 2) that improves the tour. Otherwise, it makes the most
 * promising sequential K-opt move that fulfils the positive gain criterion.
 * To prevent an infinity chain of moves the last edge in a K-opt move must
 * not previously have been included in the chain.
 *
 * The edge (t[1],t[2]) is the first edge to be exchanged. G0 is a pointer to
 * the accumulated gain.
 *
 * In case a K-opt move is found that improves the tour, the improvement of
 * the cost is made available to the caller through the parameter Gain.
 * If *Gain > 0, an improvement of the current tour has been found. In this
 * case the function returns 0.
 *
 * Otherwise, the best K-opt move is made, and a pointer to the node that was
 * connected to t[1] (in order to close the tour) is returned. The new
 * accumulated gain is made available to the caller through the parameter G0.
 *
 * The function is called from the LinKernighan function.
 */

static GainType BestG2;

static GainType BestKOptMoveRec(int k, GainType G0);

Node* BestKOptMove(Node* t1, Node* t2, GainType* G0, GainType* Gain) {
  OldSwaps = Swaps;
  PenaltyGain = 0;
  K = Swaps == 0 ? MoveType : SubsequentMoveType;
  *Gain = 0;
  t[1] = t1;
  t[2] = t2;
  T[2 * K] = 0;
  BestG2 = MINUS_INFINITY;

  /*
   * Determine (T[3],T[4], ..., T[2K]) = (t[3],t[4], ..., t[2K])
   * such that
   *
   *     G[2 * K] = *G0 - C(t[2],T[3]) + C(T[3],T[4])
   *                    - C(T[4],T[5]) + C(T[5],T[6])
   *                      ...
   *                    - C(T[2K-3],T[2K-2]) + C(T[2K-1],T[2K])
   *
   * is maximum, and (T[2K-1],T[2K]) has not previously been included.
   * If during this process a legal move with *Gain > 0 is found, then
   * make the move and exit BestKOptMove immediately.
   */

  MarkDeleted(t1, t2);
  *Gain = BestKOptMoveRec(2, *G0);
  UnmarkDeleted(t1, t2);

  if (PenaltyGain <= 0 && *Gain <= 0 && T[2 * K]) {
    int i;
    memcpy(t + 1, T + 1, 2 * K * sizeof(Node*));
    for (i = 2; i < 2 * K; i += 2) incl[incl[i] = i + 1] = i;
    incl[incl[1] = 2 * K] = 1;
    MakeKOptMove(K);
    for (i = 1; i < 2 * K; i += 2) Exclude(T[i], T[i + 1]);
    *G0 = BestG2;
    return T[2 * K];
  }
  return 0;
}

static GainType BestKOptMoveRec(int k, GainType G0) {
  Candidate* Nt2;
  Node *t1, *t2, *t3, *t4, *SUCt1;
  GainType G1, G2, G3, Gain;
  int X4, i;
  int Breadth2 = 0;

  t1 = t[1];
  t2 = t[i = 2 * k - 2];
  incl[incl[i] = i + 1] = i;
  incl[incl[1] = i + 2] = 1;
  SUCt1 = SUC(t1);
  /* Choose (t2,t3) as a candidate edge emanating from t2 */
  for (Nt2 = t2->CandidateSet; (t3 = Nt2->To); Nt2++) {
    if (t3 == t2->Pred || t3 == t2->Suc ||
        ((G1 = G0 - Nt2->Cost) <= 0 && GainCriterionUsed &&
            (k > 2 || (ProblemType != HCP && ProblemType != HPP))) ||
        Added(t2, t3))
      continue;
    if (++Breadth2 > MaxBreadth) break;
    MarkAdded(t2, t3);
    t[2 * k - 1] = t3;
    G[2 * k - 2] = G1 + t3->Pi;
    /* Choose t4 as one of t3's two neighbors on the tour */
    for (X4 = 1; X4 <= 2; X4++) {
      t4 = X4 == 1 ? PRED(t3) : SUC(t3);
      if (FixedOrCommon(t3, t4) || Deleted(t3, t4)) continue;
      t[2 * k] = t4;
      G2 = G1 + C(t3, t4);
      G3 = MINUS_INFINITY;
      if (t4 != t1 && !Forbidden(t4, t1) && !Added(t4, t1) &&
          (CurrentPenalty != 0 || TSPTW_Makespan ||
              ((!c || G2 - c(t4, t1) > 0) && (G3 = G2 - C(t4, t1)) > 0)) &&
          FeasibleKOptMove(k)) {
        if (CurrentPenalty != 0 || TSPTW_Makespan) G3 = G2 - C(t4, t1);
        if (CurrentPenalty || TSPTW_Makespan || G3 > 0) {
          MakeKOptMove(k);
          if (Improvement(&G3, t1, SUCt1)) {
            UnmarkAdded(t2, t3);
            return G3;
          }
        }
      }
      if (Backtracking && !Excludable(t3, t4)) continue;
      MarkDeleted(t3, t4);
      G[2 * k - 1] = G2 - t4->Pi;
      if (k < K) {
        Gain = BestKOptMoveRec(k + 1, G2);
        if (PenaltyGain > 0 || Gain > 0) {
          UnmarkAdded(t2, t3);
          UnmarkDeleted(t3, t4);
          return Gain;
        }
        incl[incl[1] = 2 * k] = 1;
      }
      if (t4 != t1 && !Forbidden(t4, t1) && k + 1 < NonsequentialMoveType && PatchingC >= 2 &&
          PatchingA >= 1 && (Swaps == 0 || SubsequentPatching)) {
        if (G3 == MINUS_INFINITY) G3 = G2 - C(t4, t1);
        if ((PatchingCRestricted ? G3 > 0 && IsCandidate(t4, t1) :
                                   PatchingCExtended ? G3 > 0 || IsCandidate(t4, t1) : G3 > 0)) {
          Gain = PatchCycles(k, G3);
          if (PenaltyGain > 0 || Gain > 0) {
            UnmarkAdded(t2, t3);
            UnmarkDeleted(t3, t4);
            return Gain;
          }
        }
      }
      UnmarkDeleted(t3, t4);
      if (k == K && t4 != t1 && t3 != t1 && G3 <= 0 && !Added(t4, t1) &&
          (!GainCriterionUsed || G2 - Precision >= t4->Cost)) {
        if (!Backtracking || Swaps > 0) {
          if ((G2 > BestG2 || (G2 == BestG2 && !Near(t3, t4) && Near(T[2 * K - 1], T[2 * K]))) &&
              Swaps < MaxSwaps && Excludable(t3, t4) && !InInputTour(t3, t4)) {
            if (RestrictedSearch && K > 2 && ProblemType != HCP && ProblemType != HPP) {
              /* Ignore the move if the gain does not vary */
              G[0] = G[2 * K - 2];
              G[1] = G[2 * K - 1];
              for (i = 2 * K - 3; i >= 2; i--)
                if (G[i] != G[i % 2]) break;
              if (i < 2) continue;
            }
            if (FeasibleKOptMove(K)) {
              BestG2 = G2;
              memcpy(T + 1, t + 1, 2 * K * sizeof(Node*));
            }
          }
        } else if (MaxSwaps > 0 && FeasibleKOptMove(K)) {
          Node* SUCt1 = SUC(t1);
          MakeKOptMove(K);
          for (i = 1; i < 2 * k; i += 2) {
            Exclude(t[i], t[i + 1]);
            UnmarkDeleted(t[i], t[i + 1]);
          }
          for (i = 2; i < 2 * k; i += 2) UnmarkAdded(t[i], t[i + 1]);
          memcpy(tSaved + 1, t + 1, 2 * k * sizeof(Node*));
          while ((t4 = BestSubsequentMove(t1, t4, &G2, &Gain)))
            ;
          if (PenaltyGain > 0 || Gain > 0) {
            UnmarkAdded(t2, t3);
            return Gain;
          }
          OldSwaps = 0;
          RestoreTour();
          K = k;
          memcpy(t + 1, tSaved + 1, 2 * K * sizeof(Node*));
          for (i = 1; i < 2 * K - 2; i += 2) MarkDeleted(t[i], t[i + 1]);
          for (i = 2; i < 2 * K; i += 2) MarkAdded(t[i], t[i + 1]);
          for (i = 2; i < 2 * K; i += 2) incl[incl[i] = i + 1] = i;
          incl[incl[1] = 2 * K] = 1;
          if (SUCt1 != SUC(t1)) Reversed ^= 1;
          T[2 * K] = 0;
        }
      }
    }
    UnmarkAdded(t2, t3);
    if (t3 == t1) continue;
    /* Try to delete an added edge, (_,t3) or (t3,_) */
    for (i = 2 * k - 4; i >= 2; i--) {
      if (t3 == t[i]) {
        t4 = t[i ^ 1];
        if (t4 == t1 || Forbidden(t4, t1) || FixedOrCommon(t3, t4) || Added(t4, t1)) continue;
        G2 = G1 + C(t3, t4);
        if ((!c || G2 - c(t4, t1) > 0) && (Gain = G2 - C(t4, t1)) > 0) {
          incl[incl[i ^ 1] = 1] = i ^ 1;
          incl[incl[i] = 2 * k - 2] = i;
          if (FeasibleKOptMove(k - 1)) {
            Gain = G1 + C(t3, t4) - C(t4, t1);
            MakeKOptMove(k - 1);
            if (Improvement(&Gain, t1, SUCt1)) return Gain;
          }
          incl[incl[i ^ 1] = i] = i ^ 1;
        }
      }
    }
    incl[1] = 2 * k;
    incl[2 * k - 2] = 2 * k - 1;
  }
  return 0;
}
